Precision machine vision inspection systems (or “vision systems” in short) can be utilized to obtain precise dimensional measurements of inspected objects and to inspect various other object characteristics. Such systems may include a computer, a camera and optical system, and a precision stage that is movable in multiple directions so as to allow the camera to scan the features of a workpiece that is being inspected. One exemplary prior art system that is commercially available is the QUICK VISION® series of PC-based vision systems and QVPAK® software available from Mitutoyo America Corporation (MAC), located in Aurora, Ill. The features and operation of the QUICK VISION® series of vision systems and the QVPAK® software are generally described, for example, in the QVPAK 3D CNC Vision Measuring Machine User's Guide, published January 2003, and the QVPAK 3D CNC Vision Measuring Machine Operation Guide, published September 1996, each of which is hereby incorporated by reference in their entirety. This product, as exemplified by the QV-302 Pro model, for example, is able to use a microscope-type optical system to provide images of a workpiece at various magnifications, and move the stage as necessary to traverse the workpiece surface beyond the limits of any single video image. A single video image typically encompasses only a portion of the workpiece being observed or inspected, given the desired magnification, measurement resolution, and physical size limitations of such systems.
Machine vision inspection systems generally utilize automated video inspection. U.S. Pat. No. 6,542,180 teaches various aspects of such automated video inspection and is incorporated herein by reference in its entirety. As taught in the '180 patent, automated video inspection metrology instruments generally have a programming capability that allows an automatic inspection event sequence to be defined by the user for each particular workpiece configuration. This can be implemented by text-based programming, for example, or through a recording mode which progressively “learns” the inspection event sequence by storing a sequence of machine control instructions corresponding to a sequence of inspection operations performed by a user, or through a combination of both methods. Such a recording mode is often referred to as “learn mode” or “training mode.” Once the inspection event sequence is defined in “learn mode,” such a sequence can then be used to automatically acquire (and additionally analyze or inspect) images of a workpiece during “run mode.”
The machine control instructions including the specific inspection event sequence (i.e., how to acquire each image and how to analyze/inspect each acquired image) are generally stored as a “part program” or “workpiece program” that is specific to the particular workpiece configuration. For example, a part program defines how to acquire each image, such as how to position the camera relative to the workpiece, at what lighting level, at what magnification level, etc. Further, the part program defines how to analyze/inspect an acquired image, for example, by using one or more video tools such as template matching video tools.
A part program may include, among other operations, instructions for template matching (pattern search) to identify a predefined template (pattern) in a workpiece image. The operations may include precisely determining the position of the identified workpiece pattern. Currently, template matching is carried out based on a full 2D correlation type of method. Generally in the full 2D correlation type of template matching, to match (or search) a template of T by S pixels in an image of M by N pixels, the total number of pixel-based operations required is M*N*T*S, assuming no image scaling or sub-sampling is performed prior to matching. Thus, for an image of size 640×480 pixels and a template of size 70×70 pixels, as many as 1.5 billion pixel-based operations are required, which is significant even for contemporary processors. This may result in an undue slowdown of the matching process particularly for large templates, which are becoming common as the camera resolution increases.
U.S. Pat. No. 6,128,047, incorporated herein by reference in its entirety, describes a motion estimation process and system using sparse search block and integral projection. Using integral projection in template matching operations is known to provide substantial speed increases compared to full 2D correlation types of template matching. However, known types of template matching using integral projection lack robustness when certain types of patterns are to be matched. In particular, the loss of pattern information resulting from the formation of integral projections may lead to erroneous or insufficiently accurate template matching. Lack of template matching robustness and insufficiently accurate template position determination (that is, accurate determination of the workpiece feature that matches the template) are particular problems with respect to general-purpose precision machine vision inspection systems, which are expected to provide measurements that are accurate at the pixel or subpixel resolution level for a wide variety of workpiece features.
Accordingly, a need exists for a template matching method, which provides an increased speed advantage while also ensuring robust template matching and high accuracy template position results for a wide variety of workpiece features.